A technique to detect and recognize the position, pose and shape of a specific object from an image is an important technique in computer vision. Japanese Patent Application Publication(KOKAI) No. JP-A-2003-242509 discloses a conventional pattern recognition method to recognize a registered object from an image.
This method has following properties in order to deal with partial occlusion.
The first property is to make the registration of partial information and the multiple description of a model.
The second property is to make the description of the model based on an invariant for not regulating the pose.
The third property is to enable the detection tolerance against noise.
This pattern recognition method is intended to perform object recognition and object extraction at high speed and with high accuracy by performing a distributed model representation of a partial image using a hash table for high speed retrieval of a partial template.
For registration and retrieval of partial information, a combination of three points is made for all of n image feature points to crop a partial pattern in accordance with basis vectors obtained by the combination of the three points.
However, in the above pattern recognition method, the order of the number of combinations of three feature points becomes O(n3), and there is a problem that when the number of feature points is increased, a long time and a large amount of memory for registration are required.
The left drawing of FIG. 9 is a graph of the number of combinations of three feature points and the number of feature points, and when the number of feature points is 200, the number of combinations reaches 8,000,000.
In view of speedup, in Japanese Patent Application Publication(KOKAI) No. JP-A-2003-242509, the following two methods are described.
The first approach is to adopt a technique to select feature points at random to substantially reduce the number of votes, as is adopted in Random Hough Transform.
The second approach uses various restrictions and limitations to the length, angle and the like of a vector constituting the basis information.
However, in the situation where the number of feature points becomes large, according to the first approach, a considerable number of votes are required in order to obtain sufficient accuracy. Besides, according to the second approach, there is a problem that an object in a specific direction can not be detected by the restrictions. Further, in these speedup approaches, it is not essential to reduce the number of combinations at the time of registration and is not satisfactory.